TNotes.leetcode

Appearance

0844. 比较含退格的字符串【简单】

0844. 比较含退格的字符串【简单】 ​

1. 📝 题目描述 ​

  • 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true。
  • # 代表退格字符。
  • 注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

txt
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

txt
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

txt
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

  • 1 <= s.length, t.length <= 200
  • s 和 t 只含有小写字母以及字符 '#'

进阶：

  • 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

2. 🫧 评价 ​

  • s.1 更容易理解和实现。
  • 推荐使用 s.2，它在空间复杂度上更优，是这道题的最优解法。

3. 🎯 s.1 - 栈模拟 ​

js
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function (s, t) {
  // 处理字符串，模拟退格操作
  const buildString = (str) => {
    const stack = []
    for (const char of str) {
      if (char === '#') {
        // 遇到退格符，弹出栈顶元素（如果有）
        if (stack.length > 0) {
          stack.pop()
        }
      } else {
        // 普通字符，压入栈
        stack.push(char)
      }
    }
    return stack.join('')
  }

  // 比较处理后的字符串
  return buildString(s) === buildString(t)
}
  • 时间复杂度：O(m+n)，其中 m 和 n 分别是两个字符串的长度，需要遍历两个字符串
  • 空间复杂度：O(m+n)，需要额外的栈空间存储处理后的字符

4. 🎯 s.2 - 双指针（逆向遍历） ​

js
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function (s, t) {
  let i = s.length - 1 // s的指针 - 确保指向有效字符
  let j = t.length - 1 // t的指针 - 确保指向有效字符
  let skipS = 0 // s中需要跳过的字符数
  let skipT = 0 // t中需要跳过的字符数

  while (i >= 0 || j >= 0) {
    // 在s中找到下一个有效字符
    while (i >= 0) {
      if (s[i] === '#') {
        skipS++
        i--
      } else if (skipS > 0) {
        skipS--
        i--
      } else {
        break
      }
    }

    // 在t中找到下一个有效字符
    while (j >= 0) {
      if (t[j] === '#') {
        skipT++
        j--
      } else if (skipT > 0) {
        skipT--
        j--
      } else {
        break
      }
    }

    // 比较两个有效字符
    if (i >= 0 && j >= 0 && s[i] !== t[j]) {
      return false
    }

    // 如果一个字符串已经遍历完，另一个还有有效字符，则不相等
    if (i >= 0 !== j >= 0) {
      return false
    }

    i--
    j--
  }

  return true
}
  • 时间复杂度：O(m+n)，其中 m 和 n 分别是两个字符串的长度
  • 空间复杂度：O(1)，只使用了常数个额外变量
  • 算法思路：
    1. 逆向遍历：
      • 从两个字符串的末尾开始向前遍历
      • 使用两个指针 i 和 j 分别指向字符串 s 和 t 的当前处理位置
    2. 处理退格字符：
      • 使用 skipS 和 skipT 计数器记录需要跳过的字符数量
      • 当遇到 # 时，增加对应的跳过计数
      • 当遇到普通字符且跳过计数大于 0 时，减少计数并跳过该字符
      • 只有当跳过计数为 0 时，当前字符才是有效字符
    3. 比较有效字符：
      • 在两个字符串中都找到有效字符后进行比较
      • 如果字符不相等，直接返回 false
      • 如果一个字符串已遍历完而另一个还有有效字符，也返回 false
    4. 结束条件：
      • 当两个字符串都遍历完成且所有有效字符都匹配时，返回 true

Discussions